SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Algorithm engineering</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Algorithm engineering</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Algorithm engineering</b> focuses on the design, analysis, implementation, optimization, profiling and experimental evaluation of computer <a href="Algorithms" class="mw-redirect" title="Algorithms">algorithms</a>, bridging the gap between algorithmics theory and practical applications of algorithms in <a href="Software_engineering" title="Software engineering">software engineering</a>.<sup id="cite_ref-AE_1-0" class="reference"><a href="#cite_note-AE-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

It is a general methodology for algorithmic research.<sup id="cite_ref-AEDef_2-0" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Origins">Origins</h2></div>

<p>In 1995, a report from an <a href="National_Science_Foundation" title="National Science Foundation">NSF</a>-sponsored workshop "with the purpose of assessing the current goals and directions of the Theory of Computing (TOC) community" identified the slow speed of adoption of theoretical insights by practitioners as an important issue and suggested measures to

</p>

<ul><li>reduce the uncertainty by practitioners whether a certain theoretical breakthrough will translate into practical gains in their field of work, and</li>

<li>tackle the lack of ready-to-use algorithm libraries, which provide stable, bug-free and well-tested implementations for algorithmic problems and expose an easy-to-use interface for library consumers.<sup id="cite_ref-EOTCS_3-0" class="reference"><a href="#cite_note-EOTCS-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li></ul>

<p>But also, promising algorithmic approaches have been neglected due to difficulties in mathematical analysis.<sup id="cite_ref-AEDef_2-1" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p><p>The term "algorithm engineering" was first used with specificity in 1997, with the first Workshop on Algorithm Engineering (WAE97), organized by <a href="Giuseppe_Francesco_Italiano" class="mw-redirect" title="Giuseppe Francesco Italiano">Giuseppe F. Italiano</a>.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Difference_from_algorithm_theory">Difference from algorithm theory</h2></div>

<p>Algorithm engineering does not intend to replace or compete with algorithm theory, but tries to enrich, refine and reinforce its formal approaches with <a href="Experimental_algorithmics" class="mw-redirect" title="Experimental algorithmics">experimental algorithmics</a> (also called empirical algorithmics).

</p><p>This way it can provide new insights into the efficiency and performance of algorithms in cases where

</p>

<ul><li>the algorithm at hand is less amenable to algorithm theoretic analysis,</li>

<li>formal analysis pessimistically suggests bounds which are unlikely to appear on inputs of practical interest,</li>

<li>the algorithm relies on the intricacies of modern hardware architectures like data locality, branch prediction, instruction stalls, instruction latencies which the machine model used in Algorithm Theory is unable to capture in the required detail,</li>

<li>the crossover between competing algorithms with different constant costs and asymptotic behaviors needs to be determined.<sup id="cite_ref-AE_1-1" class="reference"><a href="#cite_note-AE-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-TDEA_5-0" class="reference"><a href="#cite_note-TDEA-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Methodology">Methodology</h2></div>

<p>Some researchers describe algorithm engineering's methodology as a cycle consisting of algorithm design, analysis, implementation and experimental evaluation, joined by further aspects like machine models or realistic inputs.

They argue that equating algorithm engineering with <a href="Experimental_algorithmics" class="mw-redirect" title="Experimental algorithmics">experimental algorithmics</a> is too limited, because viewing design and analysis, implementation and experimentation as separate activities ignores the crucial feedback loop between those elements of algorithm engineering.<sup id="cite_ref-AEDef_2-2" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Realistic_models_and_real_inputs">Realistic models and real inputs</h3></div>

<p>While specific applications are outside the methodology of algorithm engineering, they play an important role in shaping realistic models of the problem and the underlying machine, and supply real inputs and other design parameters for experiments.<sup id="cite_ref-AEDef_2-3" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Design">Design</h3></div>

<p>Compared to algorithm theory, which usually focuses on the asymptotic behavior of algorithms, algorithm engineers need to keep further requirements in mind: Simplicity of the algorithm, implementability in programming languages on real hardware, and allowing code reuse.

Additionally, constant factors of algorithms have such a considerable impact on real-world inputs that sometimes an algorithm with worse asymptotic behavior performs better in practice due to lower constant factors.

</p>

<div class="mw-heading mw-heading3"><h3 id="Analysis">Analysis</h3></div>

<p>Some problems can be solved with heuristics and randomized algorithms in a simpler and more efficient fashion than with deterministic algorithms. Unfortunately, this makes even simple randomized algorithms <i>difficult to analyze because there are subtle dependencies to be taken into account</i>.<sup id="cite_ref-AEDef_2-4" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Implementation">Implementation</h3></div>

<p>Huge semantic gaps between theoretical insights, formulated algorithms, programming languages and hardware pose a challenge to efficient implementations of even simple algorithms, because small implementation details can have rippling effects on execution behavior.

The only reliable way to compare several implementations of an algorithm is to spend an considerable amount of time on tuning and profiling, running those algorithms on multiple architectures, and looking at the generated machine code.<sup id="cite_ref-AEDef_2-5" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Experiments">Experiments</h3></div>

<p>See: <a href="Experimental_algorithmics" class="mw-redirect" title="Experimental algorithmics">Experimental algorithmics</a>

</p>

<div class="mw-heading mw-heading3"><h3 id="Application_engineering">Application engineering</h3></div>

<p>Implementations of algorithms used for experiments differ in significant ways from code usable in applications.

While the former prioritizes fast prototyping, performance and instrumentation for measurements during experiments, the latter requires <i>thorough testing, maintainability, simplicity, and tuning for particular classes of inputs</i>.<sup id="cite_ref-AEDef_2-6" class="reference"><a href="#cite_note-AEDef-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Algorithm_libraries">Algorithm libraries</h3></div>

<p>Stable, well-tested algorithm libraries like <a href="Library_of_Efficient_Data_types_and_Algorithms" title="Library of Efficient Data types and Algorithms">LEDA</a> play an important role in technology transfer by speeding up the adoption of new algorithms in applications.

Such libraries reduce the required investment and risk for practitioners, because it removes the burden of understanding and implementing the results of academic research.

</p>

<div class="mw-heading mw-heading2"><h2 id="Conferences">Conferences</h2></div>

<p>Two main conferences on Algorithm Engineering are organized annually, namely:

</p>

<ul><li><a href="Symposium_on_Experimental_Algorithms" title="Symposium on Experimental Algorithms">Symposium on Experimental Algorithms (SEA)</a>, established in 1997 (formerly known as WEA).</li>

<li>SIAM Meeting on Algorithm Engineering and Experiments (ALENEX), established in 1999.</li></ul>

<p>The 1997 Workshop on Algorithm Engineering (WAE'97) was held in Venice (Italy) on September 11–13, 1997. The Third International Workshop on Algorithm Engineering (WAE'99) was held in London, UK in July 1999.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

The first Workshop on Algorithm Engineering and Experimentation (ALENEX99) was held in Baltimore, Maryland on January 15–16, 1999.<sup id="cite_ref-jhu_7-0" class="reference"><a href="#cite_note-jhu-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> It was sponsored by <a href="DIMACS" title="DIMACS">DIMACS</a>, the <a href="Center_for_Discrete_Mathematics_and_Theoretical_Computer_Science" class="mw-redirect" title="Center for Discrete Mathematics and Theoretical Computer Science">Center for Discrete Mathematics and Theoretical Computer Science</a> (at <a href="Rutgers_University" title="Rutgers University">Rutgers University</a>), with additional support from <a href="SIGACT" class="mw-redirect" title="SIGACT">SIGACT</a>, the ACM Special Interest Group on Algorithms and Computation Theory, and SIAM, the <a href="Society_for_Industrial_and_Applied_Mathematics" title="Society for Industrial and Applied Mathematics">Society for Industrial and Applied Mathematics</a>.<sup id="cite_ref-jhu_7-1" class="reference"><a href="#cite_note-jhu-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-AE-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-AE_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-AE_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">"Algorithm Engineering", Camil Demetrescu, Irene Finocchi, <a href="Giuseppe_Francesco_Italiano" class="mw-redirect" title="Giuseppe Francesco Italiano">Giuseppe F. Italiano</a>, web: <a rel="nofollow" class="external text" href="http://www.dis.uniroma1.it/~demetres/docs/ae.pdf">http://www.dis.uniroma1.it/~demetres/docs/ae.pdf</a></span>

</li>

<li id="cite_note-AEDef-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-AEDef_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-AEDef_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-AEDef_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-AEDef_2-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-AEDef_2-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-AEDef_2-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-AEDef_2-6"><sup><i><b>g</b></i></sup></a></span> <span class="reference-text">"Algorithm Engineering – An Attempt at a Definition", <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Peter Sanders</a>, web: <a rel="nofollow" class="external text" href="http://algo2.iti.kit.edu/documents/definition.pdf">http://algo2.iti.kit.edu/documents/definition.pdf</a></span>

</li>

<li id="cite_note-EOTCS-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-EOTCS_3-0">^</a></b></span> <span class="reference-text">"Emerging Opportunities for Theoretical Computer Science", Aho, Johnson, Karp, Kosaraju, McGeoch, Papadimitriou, web: <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20180927054846/http://www.dsi.unive.it/~wae97/">"Workshop on Algorithm Engineering"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.dsi.unive.it/~wae97">the original</a> on 2018-09-27<span class="reference-accessdate">. Retrieved <span class="nowrap">2009-09-14</span></span>.</cite></span>

</li>

<li id="cite_note-TDEA-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-TDEA_5-0">^</a></b></span> <span class="reference-text">"Towards a Discipline of Experimental Algorithmics", Bernard M. E. Moret, web: <a rel="nofollow" class="external text" href="http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf">http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf</a></span>

</li>

<i>Algorithm engineering: 3rd International Workshop</i>,

Jeffrey Scott Vitter, Christos D. Zaroliagis, 1999, web:

<a rel="nofollow" class="external text" href="https://books.google.com/books?id=UZHUQFy8cWsC">BGoogle-sC</a>.</span>

</li>

"Workshop on Algorithm Engineering and Experiments"

(overview), JHU.edu, 1999, web:

<a rel="nofollow" class="external text" href="http://www.cs.jhu.edu/Conferences/ALENEX99/">JHU-ALENEX99</a>.</span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-03-04" href="https://en.wikipedia.org/wiki/?title=Algorithm_engineering&oldid=1211852014">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>